#include<iostream.h>
#include<conio.h>
#include"BSTree.h"
#include"display.h"
//#include"queue.h"
// inserts the values in the binary search tree , works in a non-recursive manner , matches the given value with root value and takes decision accordingly
                                                                               //  and then goes right of left , finally adds the newNode as the leaf node
void BSTree :: insert(Node **root, int value)
{
     
     Node *newNode = new Node;
     newNode->data = value;
     newNode->left = newNode->right = NULL;
     Node *currNode = new Node;
     currNode = *root;
     if(*root == NULL)
         *root = newNode;
     else
     {
         while(currNode)
         {//cout<<"1";
             if((currNode->left == NULL) && (currNode->right == NULL))
                  break;
             else if(currNode->left && currNode->data > value)
                 currNode = currNode->left;
             else if(currNode->right && currNode->data < value)
                 currNode = currNode->right;
             else 
                 break;
         }
         if(currNode->data > value)
            currNode->left = newNode ;
         else
             currNode->right = newNode;
     }
}
void BSTree :: insert(int value)
{
     insert(&root, value);
}
// searches the tree for a given value , if found then returns value 1 , if not found then returns value 0
bool BSTree :: isFoundValue(Node *root, int value)
{//cout<<"5";
       if(root == NULL)
            return (1==2);
       else if(root->data == value)
           return (root->data == value);
       else if(root->data < value)
              return isFoundValue(root->right, value);
       else 
             return isFoundValue(root->left, value);
       
}
bool BSTree :: isFoundValue(int value)
{
    return isFoundValue(root, value);
}
// finds the minimum value in the binary search tree, traverses in the left child until it reaches to the NULL , and then returns the leftmost value
int BSTree :: findMinValue(Node *root)
{
    while(1)
    {
            if(root->left != NULL)
               root = root->left;
            else
                break;
    }
    return root->data;
}
int BSTree :: findMinValue()
{
    return findMinValue(root);
}
// finds the maximum value in the binary search tree, traverses in the right child until it reaches to the null , and returns the rightmost value
int BSTree :: findMaxValue(Node *root)
{
    while(1)
    {
            if(root->right != NULL)
                root = root->right;
            else
                break;
    }
    return root->data;
}
int BSTree :: findMaxValue()
{
    return findMaxValue(root);
}
//int BSTree :: KthSmallestValue(Node *root, int k, int elemCounter)
//{//cout<<"6";
//
//}
//int BSTree :: KthSmallestValue(int k)
//{
//    int elemCounter = 0;
//    return KthSmallestNode(root, k, elemCounter);
//}

int main()
{
    BSTree bstree;
    bstree.insert(5);
    bstree.insert(9);
    bstree.insert(8);
    bstree.insert(10);
    bstree.insert(3);
    bstree.insert(4);
    bstree.insert(2);
    bstree.inorderDisplay();
    bstree.preorderDisplay();
    bstree.postorderDisplay();
    cout<<"\n\n is value 5 found = "<< bstree.isFoundValue(5);
    cout<<"\n is value 7 found = "<< bstree.isFoundValue(7);
    cout<<"\n min value in tree = "<< bstree.findMinValue();
    cout<<"\n max value in tree = "<<bstree.findMaxValue();
   // cout<<"\n 4 th smallest element = "<<bstree.KthSmallestValue(4);
    getch();
    return 0;
}
